iT邦幫忙

2022 iThome 鐵人賽

DAY 19
0

走出迷宮
給予一個二維整數陣列,以1表示牆壁,0表示通道,構成一個迷宮。你可以用直角方向(上u,下d,左l,右r)在迷宮中移動,想辦法從入口走到出口。入口座標固定為(0,1),出口座標固定為(N-2, M-1)如下所示:
N為5
M為7
1 0 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 1 1 1
1 0 1 0 0 0 0
1 1 1 1 1 1 1

給你一個N×M的迷宮(3 <= N,M <= 9,N,M為奇數),你必須求出從入口走到出口的路徑,上例的解答輸出為drrddrrr

範例輸入
5
7
1 0 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 1 1 1
1 0 1 0 0 0 0
1 1 1 1 1 1 1

範例輸出
drrddrrr

#include <stdio.h>
void f(char a1[],int b1[][9],int M,int N,int x,int y,int *path){
    int i=0;

    b1[x][y]=2;
    //printf("%d,%d\n",x,y);
    if(x==M-2&&y==N-1){
        for(i=0;i<(*path);i++)
            printf("%c",a1[i]);
    }
    else{
        //上
        int nxt_x,nxt_y;
        nxt_x=x-1;
        nxt_y=y;
        if(nxt_x>=0){
            if(b1[nxt_x][nxt_y]==0){
                a1[(*path)++]='u';
                f(a1,b1,M,N,nxt_x,nxt_y,path);
            }
        }
        //左
        nxt_x=x;
        nxt_y=y-1;
        if(nxt_y>=0){
            if(b1[nxt_x][nxt_y]==0){
                a1[(*path)++]='l';
                f(a1,b1,M,N,nxt_x,nxt_y,path);
            }
        }
        //下
        nxt_x=x+1;
        nxt_y=y;
        if(nxt_x<M){
            if(b1[nxt_x][nxt_y]==0){
                a1[(*path)++]='d';
                f(a1,b1,M,N,nxt_x,nxt_y,path);
            }
        }
        //右
        nxt_x=x;
        nxt_y=y+1;
        if(nxt_y<N){
            if(b1[nxt_x][nxt_y]==0){
                a1[(*path)++]='r';
                f(a1,b1,M,N,nxt_x,nxt_y,path);
            }
        }
    }
    (*path)--;
}

int main(){
    int b1[9][9],i,j,M,N,path=0;
    char a1[99];
    scanf("%d%d",&M,&N);
    for(i=0;i<M;i++){
        for(j=0;j<N;j++){
            scanf("%d",&b1[i][j]);
        }
    }
    f(a1,b1,M,N,0,1,&path);

    return 0;
}

上一篇
[Day18]五子棋
下一篇
[Day20]數獨
系列文
環島C一下自己的人生24
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言